package 纯数组;

public class No169多数元素 {

    /**
     * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     * 示例 1：
     * 输入：[3,2,3]
     * 输出：3
     * 示例 2：
     * 输入：[2,2,1,1,1,2,2]
     * 输出：2
     *  
     * 进阶：
     * 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
     */

    public int majorityElement(int[] nums) {

        int num=nums[0];
        int count=1;

        for (int i = 1; i < nums.length; i++) {
            if(num==nums[i]){
                count++;
            }else{
                count--;
            }
            if(count<0){
                num=nums[i];
                count++;
            }
        }

        return num;
    }

    public static void main(String[] args) {
        No169多数元素 n=new No169多数元素();
        int[] arr={2,2,2,2,2,2,3,3,3,1};
        int result = n.majorityElement(arr);
        System.out.println(result);
    }

}
